package leetcode_5000;

import java.util.LinkedList;
import java.util.Queue;

public class RemoveOutermostParentheses_5016 {
	public static void main(String[] args) {
		RemoveOutermostParentheses_5016 test = new RemoveOutermostParentheses_5016();
		System.out.println(test.removeOuterParentheses("(()())(())(()(()))"));
		System.out.println(test.removeOuterParentheses("(()())(())"));
		System.out.println(test.removeOuterParentheses("()()"));
	}
	public String removeOuterParentheses(String S) {
        char[] chars = S.toCharArray();
        Queue<Character> queue = new LinkedList<Character>();
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for(char c:chars) {
        	if(c == '(') {
        		queue.offer('(');
        		++count;
        	}else {
        		--count;
        		if(count == 0) {//出队
        			queue.poll();
        			while(!queue.isEmpty()) {
        				sb.append(queue.poll());
        			}
        		}else {
        			queue.offer(')');
        		}
        	}
        }
        return sb.toString();
    }
}
